package com.leetcode.dp;

import java.util.Arrays;

/**
 * @author Dennis Li
 * @date 2020/7/20 16:49
 */
public class TargetSum_494 {

    // 动态规划：优先考虑用二维数组来表示，再考虑数组降维
    // 一个是跟坐标有关系，一个是跟和有关系，可以考虑结合坐标+和来建立二维DP数组
    public int findTargetSumWays(int[] nums, int S) {
        // 正负和公式运用 -- 详情见答案推断
        int sum = Arrays.stream(nums).sum();
        if(sum < S || ((sum + S) & 1) == 1) return 0;
        int W = (S + sum) >> 1;
        int[] dp = new int[W + 1];
        dp[0] = 1;
        for (int num : nums) {
            // 背包问题的方程是根据和来构建，而不是序号
            for (int i = W; i >= num ; i--) {
                dp[i] = dp[i] + dp[i - num];
            }
        }
        return dp[W];
    }


    int res = 0;
    int S = 0;

    public int findTargetSumWays2(int[] nums, int S) {
        this.S = S;
        dfs(0, nums, 0);
        return res;
    }

    public void dfs(int sum, int[] nums, int index) {
        if (index == nums.length) {
            if (sum == S) res++;
            return;
        }
        dfs(sum + nums[index], nums, index + 1);
        dfs(sum - nums[index], nums, index + 1);
    }

}
